#include <iostream>
#include <algorithm>

using namespace std;
const int N = 500 * 500 + 10;

int fa[510];
int ca, n;
int pos;
struct node{
	int a, b, c;
}a[N];
int ret, cnt;

bool cmp(node& x, node& y)
{
	return x.c < y.c;
}

int find(int x)
{
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void kruskal()
{
	sort(a + 1, a + 1 + pos, cmp);
	for(int i = 1; i <= pos; i++)
	{
		int x = a[i].a, y = a[i].b, c = a[i].c;
		int fx = find(x), fy = find(y);
		if(fx != fy)
		{
			cnt++;
			ret += c;
			fa[fx] = fy;
		}
	}
}

int main()
{
	cin >> ca >> n;
	for(int i = 1; i <= n; i++) fa[i] = i;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			int z; cin >> z;
			if(i >= j || z == 0 || z > ca) continue;
			a[++pos].a = i; a[pos].b = j; a[pos].c = z;
		}
	}
	
	kruskal();
	cout << ret + (n - cnt) * ca << endl; 
	return 0; 
}
